package LeetCode;
import java.util.*;
public class LeetCodeMain2 {
    List<List<Integer>> list1=new ArrayList<>();
    List<Integer> list2=new ArrayList<>();
    List<String> list3=new ArrayList<>();
    StringBuilder st=new StringBuilder();
    String[] str1=new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        int n=digits.length();
        if (n==0||digits==null){
            return list3;
        }
        backtracking(digits,0);
        return list3;
    }
    public void backtracking(String digits,int startIndex){
        if (st.length()==digits.length()){
            list3.add(st.toString());
            return;
        }
        int index=digits.charAt(startIndex)-'0';
        for (int i = 0; i < str1[index].length(); i++) {
            st.append(str1[index].charAt(i));
            backtracking(digits,startIndex+1);
            st.deleteCharAt(st.length()-1);
        }
    }

    public static void main(String[] args) {
        StringBuilder st=new StringBuilder();
        st.append(1);
        st.append(2);
        st.append(3);
        st.append(4);
        st.append(5);
        st.append(6);
        st.append(7);
        System.out.println(st.toString());
        System.out.println(st.deleteCharAt(st.length()-1).toString());
    }
    public void backtracking2(int n, int k, int startIndex) {
        if (list2.size()==k){
            int sum=0;
            for (int num:list2) {
                sum+=num;
            }
            if (sum==n){
                list1.add(new ArrayList<Integer>(list2));
            }
            return;
        }
        for (int i = startIndex; i <=9-(k-list2.size())+1; i++) {
            list2.add(i);
            backtracking2(n,k,i+1);
            list2.remove(list2.size()-1);
        }
    }
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking2(n,k,1);
        return list1;
    }
    public void backtracking1(int n, int k, int startIndex){
        if (list2.size()==k){
            list1.add(new ArrayList<Integer>(list2));
            return;
        }
        for (int i = startIndex; i <=n; i++) {
            list2.add(i);
            backtracking1(n,k,i+1);
            list2.remove(list2.size()-1);

        }
    }
    public List<List<Integer>> combine(int n, int k) {
        backtracking1(n,k,1);
        return list1;
    }
}
